• 先簡單回顧一下，今天預計分析的題目： 53. Maximum Subarray

• 題目敘述：https://leetcode.com/problems/maximum-subarray/

• 題目敘述：

  • 題目會給一個 nums 的 list，需要找出至少一個數字的連續值，他們相加的結果會是最大的
    

• 測資的 Input/Output

  • 會給一個 nums 的 list，需要回傳連續相加最大的值
    

• 這種題目「暴力的解法」就是把每個相加的值儲存起來，找出最大的值 (max)
  

• 若有N筆資料，那暴力解法的

  • 時間成本：需要兩個迴圈，大約 O(N^2)
  • 空間成本：需要 N*N 的空間

• 由於他是要算最佳解，我們只要記錄 max 即可

  • 我們從第2個位置( index = 1 )開始讀取 nums
    • 若前一個位置大於 0 (才有累加的價值)，就將此位置+前一個位置的值
    • 若前一個位置小於等於 0 (沒有必要累加)，就不用理他，此位置就保持原狀
      

• python 實作

    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            for i in range (1, len(nums)):
                if(nums[i-1] > 0):
                    nums[i] = nums[i]+nums[i-1]
                    
            return max(nums)